#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

#define NMAX 500002


void
swap_ints(int* a, int * b)
{
	int T = *a;
	*a = *b;
	*b = T;
}



/*void
Quick_sort__main_(int * a, int L, int R)
{
	int pivot = a[(rand() % (R-L)) + L];
	int i = L,
	    j = R;

	do {
		while (a[i] < pivot && i <= j)
			++i;
		while (a[j] > pivot && j <= i)
			--j;
		if (i <= j) {
			swap_ints(&a[i], &a[j]);
			++i;
			--j;
		}
	} while (i <= j);

	if (L < j)
		Quick_sort__main_(a, L, j);
	if (i < R)
		Quick_sort__main_(a, i, R);
}*/



int
Quick_sort__partition(int * array, int L, int R)
{
	int p = array[(rand() % (R-L)) + L];
	register int i = L, j = R;
	while (i <= j) {
		while (array[i] < p)
			++i;
		while (array[j] > p)
			--j;
		if (i < j) {
			swap_ints(&array[i], &array[j]);
			++i;
			--j;
		} else
			return j;
	}
	return j;
}



void
Quick_sort__main(int *array, int left, int right)
{
	int m;

	if (left < right) {
		m = Quick_sort__partition(array, left, right);
		Quick_sort__main(array, left, m);
		Quick_sort__main(array, m+1, right);
	}
	return;
}



void
Quick_sort(int * array, int size)
{
	return Quick_sort__main(array, 0, size-1);
}



int
main(void)
{
	int array[NMAX];
	int n;
	clock_t start_time = clock(), end_time;
	register int i = 0;
	(void) freopen("qsort.in", "r", stdin);
	(void) freopen("qsort.out", "w", stdout);

	(void)scanf("%d", &n);
	while (i<n)
		(void)scanf("%d", &array[i++]);

	Quick_sort(array, n);
	for (i = 0; i < n ; ++i) {
		(void)printf("%d ", array[i]);
	}
	putchar('\n');
	end_time = clock();
	fprintf(stderr, "\ttime: %.5lf\n", ((double)(end_time - start_time) / CLOCKS_PER_SEC));
	return 0;
}
